package pers.vic.basics.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Vic.xu
 * @description:22. 括号生成
 * @date: 2020/11/11  14:44
 */
public class J0022_M_GenerateParenthesis {

    /*
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     */

    /**
     * 1. 左括号和右括号的数量都不能大于n
     * 2. 进入node的时候，左括号数量 < n 则添加左括号
     * 3. 进入node的时候，左括号大于右括号，可以添加右括号
     */
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n <= 0) {
            return res;
        }
        StringBuilder temp = new StringBuilder();
        dfs(n, n, temp, res);
        return res;
    }

    public static void dfs(int left, int right, StringBuilder temp, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(temp.toString());
            return;
        }
        //先放left
        if (left > 0) {
            temp.append("(");
            dfs(left - 1, right, temp, res);
            temp.setLength(temp.length() - 1);
        }
        //当剩余left比剩余right少 这个时候放right
        if (left < right) {
            temp.append(")");
            dfs(left, right - 1, temp, res);
            temp.setLength(temp.length() - 1);
        }
    }


    public static void main(String[] args) {
        generateParenthesis(3).forEach(System.out::println);
    }


}
